import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
    Queue<Integer> min;
    Queue<Integer> max;
    public MedianFinder() {
        min=new PriorityQueue<>();
        max=new PriorityQueue<>((x,y)->(y-x));
    }

    public void addNum(int num) {
        if(min.size()!=max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        return min.size()!=max.size()?min.peek():(min.peek()+max.peek())/2.0;
    }
}




















class MedianFinder1 {
    Queue<Integer> min;
    Queue<Integer> max;
    /** initialize your data structure here. */
    public MedianFinder1() {
        min=new PriorityQueue<>();
        max=new PriorityQueue<>((x,y)->(y-x));
    }

    public void addNum(int num) {
        if(min.size()!=max.size()){
            min.add(num);
            max.add(min.poll());
        }else{
            max.add(num);
            min.add(max.poll());
        }
    }

    public double findMedian() {
        return min.size()!=max.size()?min.peek():(min.peek()+max.peek())/2.0;
    }
}








public class project {
    public int maximalRectangle(char[][] matrix) {
        int row=matrix.length;
        if(row==0){
            return 0;
        }
        int col=matrix[0].length;
        int[][] arr=new int[row][col];
        int ret=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j]=='1'){
                    arr[i][j]=(j==0?0:arr[i][j-1])+1;
                }
            }
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i][j]=='0'){
                    continue;
                }
                int cur=arr[i][j];
                int prev=cur;
                for(int k=i-1;k>=0;k--){
                    cur=Math.min(cur,arr[k][j]);
                    prev=Math.max(prev,(i-k+1)*cur);
                }
                ret=Math.max(prev,ret);
            }
        }
        return ret;
    }














    public int maximalRectangle1(String[] matrix) {
        int row=matrix.length;
        if(row==0){
            return 0;
        }
        int col=matrix[0].length();
        int[][] arr=new int[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i].charAt(j)=='1'){
                    arr[i][j]=(j==0?0:arr[i][j-1])+1;
                }
            }
        }
        int ret=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(matrix[i].charAt(j)=='0'){
                    continue;
                }
                int cur=arr[i][j];
                int prev=cur;
                for(int k=i-1;k>=0;k--){
                    cur=Math.min(cur,arr[k][j]);
                    prev=Math.max(prev,(i-k+1)*cur);
                }
                ret=Math.max(ret,prev);
            }
        }
        return ret;
    }














    public int[] sortArrayByParity(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while (left<right){
            while (left<right&&nums[left]%2==0){
                left++;
            }
            while (left<right&&nums[right]%2==1) {
                right--;
            }
            int tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;
        }
        return nums;
    }
}
